package ch4tree;

public class Ex7 {

	static boolean compareTrees(TreeNode target, TreeNode query) {
		if (target == null) {
			return query == null;
		}
		else if (target.val == query.val) {
			if (matchTreesR(target, query)) {
				return true;
			}
		}
		
		boolean lmatch = compareTrees(target.left, query);
		if (lmatch) {
			return true;
		}
		
		return compareTrees(target.right, query);
	}
	
	static boolean matchTreesR(TreeNode target, TreeNode query) {
		boolean match = compareTrees(target.left, query.left);
		if (match) {
			match &= compareTrees(target.right, query.right);
		}
		return match;
	}
	
	public static void main(String ...strings ) {
//	        4               
//	       / \       
//	      /   \      
//	     /     \     
//	    /       \    
//	    2       6       
//	   / \     / \   
//	  /   \   /   \  
//	  1   3   5   7   
//	               \ 
//	               8 

		TreeNode target = Chapter.createMinimalBST(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
		BTreePrinter.printNode(target);

//		    6       
//		   / \   
//		  /   \  
//		  5   7   
//		       \ 
//		       8		
		TreeNode query = Chapter.createMinimalBST(new int[] { 5, 6, 7, 8 });
		BTreePrinter.printNode(query);
		
		boolean matchTrees = compareTrees(target, query);
		int a=0;
	}
}
